package com.future;

import java.util.ArrayList;
import java.util.List;

/**
 * Description: 216. ����ܺ� III
 * �ҳ��������֮��Ϊ?n ��?k?��������ϣ�����������������
 * <p>
 * ֻʹ������1��9
 * ÿ������?���ʹ��һ��?
 * ���� ���п��ܵ���Ч��ϵ��б� �����б��ܰ�����ͬ��������Σ���Ͽ������κ�˳�򷵻ء�
 * <p>
 * ʾ�� 1:
 * <p>
 * ����: k = 3, n = 7
 * ���: [[1,2,4]]
 * ����:
 * 1 + 2 + 4 = 7
 * û���������ϵ�����ˡ�
 * <p>
 * ��Դ�����ۣ�LeetCode��
 * ���ӣ�https://leetcode.cn/problems/combination-sum-iii
 * ����Ȩ������������С���ҵת������ϵ�ٷ���Ȩ������ҵת����ע��������
 *
 * @Author: future
 * @Date:2022/5/14:0:20
 */
public class Solution_216 {

    public static void main(String[] args) {
        //int k = 3,n = 7;
        int k = 3, n = 9;
        System.out.println(combinationSum3(k, n));
    }

    public static List<List<Integer>> combinationSum3(int k, int n) {
        if (n <= 0 || k <= 0) {
            return new ArrayList<>();
        }
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < 9; i++) {
            list.add(i + 1);
        }
        List<List<Integer>> ans = new ArrayList<>();
        process(0, k, n, ans, new ArrayList<Integer>());
        return ans;
    }

    private static void process(int index, int k, int rest, List<List<Integer>> ans, List<Integer> tmpAns) {
        if (tmpAns.size() == k || index == 9 || rest < 0) {
            if (tmpAns.size() == k && rest == 0) {
                List<Integer> tmp = new ArrayList<Integer>() {{
                    addAll(tmpAns);
                }};
                ans.add(tmp);
            }
            return;
        }
        // ��ѡ
        process(index + 1, k, rest, ans, tmpAns);
        // ѡ
        tmpAns.add(index + 1);
        process(index + 1, k, rest - (index + 1), ans, tmpAns);
        tmpAns.remove(tmpAns.size() - 1);
    }
}
